package retrospection.分割回文串;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 */
public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), ans);
        return ans;
    }

    void backtrack(String s, int start, List<String> temp, List<List<String>> ans) {
        if (start == s.length()  ) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start + 1 ; i <= s.length(); i++) {
            String substring = s.substring(start, i);
            if (!isPalindrome(substring)){
                continue;
            }
            temp.add(substring);
            backtrack(s, i, temp, ans);
            temp.remove(temp.size() - 1);
        }
    }

    boolean isPalindrome(String s){
        int start = 0 ;
        int end = s.length()-1;
        while (start < end){
            if (s.charAt(start) != s.charAt(end)){
                return false;
            }
            start ++;
            end--;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.partition("aab"));
    }

}
